\documentclass[a4paper,12pt]{article}

\usepackage{latexsym}

\usepackage[top=3cm, bottom=3cm, left=2cm, right=2cm]{geometry} 

\usepackage[spanish]{babel}

\usepackage[utf8]{inputenx}

\usepackage{graphicx}

% Para los diagramas de flujo:
\usepackage{tikz}
\usetikzlibrary{shapes,arrows,positioning}

\author{Martín Buchwald \\ Ezequiel Genender Peña \\ Jennifer Woites}

\title{75.59 Técnicas de Programación Concurrente I\\
	\textbf{Primer Proyecto}\\
	Facultad de Ingeniería, Universidad de Buenos Aires
	\date{Cuatrimestre I, 2014}
}


\begin{document}

\maketitle
\thispagestyle{empty}
\newpage
\tableofcontents
\newpage

\section{Análisis del Problema}
El problema consiste en simular una estación de servicio, teniendo que manejar los problemas de concurrencia que puedan aparecer, utilizando las técnicas analizadas en la materia (y que fueron especificadas en el enunciado). Es necesario analizar cómo sincronizar y comunicar a los distintos procesos, para que la ejecución sea \underline{correcta}.\\
Problemas de concurrencia que pueden aparecer:
\begin{itemize}
	\item Varios empleados pueden querer utilizar los surtidores al mismo tiempo (un recurso
	 limitado).
	\item El jefe debe poder saber si los empleados están todos ocupados, o hay al menos uno
	 libre.
	\item Siguiendo al punto anterior, si no hay empleados libres	 asignarle a alguno el auto,
	 mientras que al mismo tiempo puede haber un empleado que acaba de terminar su tarea.
	\item Varios empleados pueden estar libres al mismo tiempo a la espera de un auto a ser
	 atendido. Es necesario que en tal caso los empleados actuen de manera sincronizada.
	\item Varios empleados, y el administrador, querrán acceder a la caja, por lo que será
	necesario sincronizar tal acceso.
	\item Podrían llegar autos a la estación de servicio mientras el Jefe está asignándole
	otro a un empleado. 
\end{itemize}
A su vez, es necesario determinar la condición de finalización de la simulación. Dado que no hay una especificación dentro del enunciado acerca de tal tema, hemos optado por finalizar la simulación luego de pasado un tiempo (en segundos), pasado por parámetro al programa. Será necesario que tal finalización sea también correcto; es decir, que todos los procesos finalicen sus funciones de la manera esperada, de una u otra forma dependiendo del proceso que se trate.

\subsection{Especificación}
Hay que poner lo de los casos de uso...... 

\section{Resolución de Tareas}
\subsection{División de proyecto en procesos}
Luego de haber analizado el proyecto, decidimos dividirlo en los siguientes procesos:
\begin{enumerate}
	\item Un proceso que simule la estación de servicio en sí. Dado ésto, tal proceso será el
	principal, o dicho de otro modo, el \textit{padre} de los demás procesos del programa
	(teniendo que crearlos una vez que se inicia la simulación).
	\item Un proceso que se encargue de generar los autos, cada un cierto tiempo aleatorio.
	Tales autos deberán ser enviados al Jefe para que éste los trate.
	\item Un proceso que maneje al Jefe. Esto quiere decir: obtener los autos
	generados por el proceso anterior, y analizar si hay empleados disponibles. En caso
	afirmativo, debe enviarle a algún empleado el auto, y en caso negativo desestimar el
	pedido y quedar a la espera de otro auto.
	\item N procesos que se encarguen de manejar a los empleados. Estos deben quedar a la
	espera de un auto a ser atendido, indicando su disponibilidad (que luego se analizará cómo
	lograremos ésto). Luego de obtener un auto a atender, debe proceder como está especificado
	en el enunciado.
	\item Un proceso que maneje al administrador, el cual irá a la caja a ver su monto cada
	cierto tiempo aleatorio.
\end{enumerate}


\subsection{Comunicación entre procesos}
Los procesos que se deben comunicar entre sí son:
\begin{itemize}
	\item Estación de Servicio - Generador de autos: debe poder indicarle cuando debe terminar
	de generar autos.
	\item Generador de Autos - Jefe: debe enviarle el auto que ha generado.
	\item Generador de Autos - Jefe: El generador debe comunicarle al jefe, de alguna manera,
	que	la simulación no ha terminado y por consiguiente no se generarán más autos.
	\item Jefe - Empleados: debe poder conocer la disponibilidad de los empleados, para saber
	si enviarles el auto, o despacharlo. Por lo tanto, el dato de la cantidad de empleados
	disponibles es algo que deben comunicarse entre Empleados y el Jefe.
	\item Jefe - Empleados: Una vez determinado que un empleado puede hacerse cargo del auto, 
	el jefe debe enviar el auto.
	\item Jefe - Empleados: El jefe debe comunicarle a los empleados, de alguna manera, que
	la simulación ha terminado y por consiguiente no es necesario que sigan esperando por
	otros autos. 
	\item Empleados entre sí: los empleados deben comunicarse entre sí para poder ver cuáles
	surtidores están libres y cuales no. Mientras no hayan surtidores libres deberán quedarse
	los restantes empleados esperando a que esta situación cambie. Además, otro dato que deben
	compartir es cuáles son los surtidores libres y cuáles los ocupados.
	\item Empleados entre sí, con el Administrador: Deben poder entre todos ellos acceder a
	la caja de manera sincronizada. Además deben compartir entre ellos el dato del monto de
	la caja en cada momento (puesto que los empleados lo aumentan, y el administrador lo
	consulta).
	\item Estación de Servicio - Administrador: La estación de servicio debe poder avisarle
	al administrador que la simulación ha terminado, y por consiguiente debe terminar su
	ejecución.
\end{itemize}

\subsection{Mapeo de problemas}
Luego de analizar los problemas con los que nos encontramos, podemos hacer el siguiente mapeo con los problemas conocido de concurrencia:
\begin{itemize}
	\item La relación entre los Empleados y el Jefe puede mapearse con el problema de \textbf{Productores y Consumidores}, aunque visto desde una perspectiva un poco anti-intuitiva: los empelados producen su disponibilidad, mientras que el jefe la consume. Esto puede verse de la \textit{lectura destructiva} del jefe, dado que va reduciendo tal valor a medida que la lee, y la producción y el consumo son operaciones excluyentes, como es especificado en las características del problema.
	\item La relación entre los Empleados y el Administrador puede mapearse como el problema de \textbf{Lectores y Escritores}, siendo el Administrador el Lector y los Empleados los Escritores, dado que los escritores pueden escribir de a uno a la vez (condición del problema), y no es verdad que los lectores no puedan leer todos al mismo tiempo (también condición del problema), dado que en este caso particular hay un único lector. Notar que además la lectura del Administrador no es destructiva, lo cual también es condición del problema.
	\item La relación entre los mismos Empleados, en función de su manejo con los surtidores, puede mapearse al problema de \textbf{Productores y Consumidores}, con una vuelta de tuerca: los empleados van oscialando entre la posición de Productores y Consumidores. Cuando quieren obtener un surtidor, estarán consumiendo el surtidor. Cuando lo liberen, estarán permitiendo que otro empleado (o incluso él mismo) lo utilice. Básicamente, el producto en cuestión es la disponibilidad de los surtidores, que es consumida y producida por los mismos empleados.
\end{itemize}


\subsection{Mecanismos de concurrencia para la comunicación}
A continuación se comentan la comunicación que debe haber entre procesos, así como los mecanismos de concurrencia adoptados para resolver tal comunicación. Es importante notar que cada vez que se hable de utilizar Memoria Compartida para comunicar datos entre procesos, habrá un Semáforo binario interviniendo para manejar el sincronismo de acceso a la memoria compartida. De ahora en más se deja implícito ésto, pero es de remarcada importancia no olvidar que siempre estará presente este hecho. Además, se le agrega a la memoria compartida la funcionalidad de poder incrementar el valor actual que tiene. Esto se hace porque pueden haber errores de concurrencia si primero leyéramos el dato actual, y luego escribiéramos (el dato reciéntemente leido podría pasar a ser inválido). Por esto, se agrega tal funcionalidad, la cual realiza ambas operaciones, protegidas en conjunto por el semáforo incorporado a la memoria compartido. 

\subsubsection{Generador de Autos - Jefe}
Una vez iniciada la simulación, el generador de autos le irá mandando, cada cierto tiempo aleatorio \footnote{Se modela la llegada de autos como correspondiente a un proceso puntual de Poisson, por lo tanto, el tiempo de espera hasta que llegue un nuevo auto corresponde a una variable aleatoria de distribución exponencial, por lo que luego de enviar un auto se realiza una simulación de tal variable, para ver el tiempo de espera para craer el siguiente auto.}
el cual debe poder obtenerlo. Por lo tanto, se realiza esta comunicación con un Pipe, en el cual el Generador escribe y el Jefe lee. De esta manera, el jefe puede realizar sus tareas de asignación mientras el generador le envía un nuevo auto, o incluso se logra que mientras no llegue un nuevo auto a ser atendido, el jefe quede en estado bloquedo, lo cual es lo deseado dado que el Jefe no tendrá nada que hacer en esos momentos.

\subsubsection{Jefe - Empleados}
Una vez que el Jefe tiene un auto para ser atendido, debe analizar si hay empleados disponibles. Es importante notar que al Jefe no le interesa saber qué empleados están disponibles, sino cuántos (o mejor dicho, saber si tal cantidad es igual o mayor que 0). Para poder comunicar esta información, crucial para la simulación, entre los empleados al jefe, se dispone del uso de una memoria compartida, para un simple valor entero. Cada vez que un empleado pasa a estar disponible (puesto que ya terminó con sus tareas), aumentará en 1 el valor de tal memoria (que iniciará en 0). Cuando el Jefe necesite ver si hay algún empleado disponible, verá el contenido de tal memoria compartida. Si es igual a 0, no hay ningún empleado libre actualmente, por lo que se despacha al auto, y el jefe espera a que llegue otro auto para ser atendido (como fue explicado anteriormente). Si es mayor a 0, se restará tal valor en una unidad (puesto que habrá un empleado menos disponible), y se le envía a los empleados el auto. 

Es muy importante notar que no pueden ser los empleados los encargados de disminuir su disponibilidad, por más que a priori suene lo más intuitivo. Proponemos el siguiente ejemplo, siendo el empleado quien disminuye su disponibilidad: supongamos el caso de tener un único empleado, el cual se encuentra inicialmente disponible. El jefe verá que la disponibilidad será de 1 empleado, por lo que envía el auto. Supongamos también que \textit{el empleado es muy lento}, y no llega a disminuir su disponibilidad antes que el jefe vuelva a tener otro auto para atender, por lo que éste volvería a ver la disponibilidad de empleados en 1, cuando este no es cierto. Por esta razón es importante ver que debe ser el jefe quien disminuye la disponibilidad. Otra forma de verlo es viéndolo desde el lado del análisis de mapeo a problemas conocidos de concurrencia: el jefe es el que \textit{consume} la disponibilidad de los empleados, mientras que los empleados la \textit{crean}. Evidentemente, al ser el jefe quien la consume, debe ser éste quien disminuya su valor.

Además el jefe deberá poder enviar los autos a los empleados. Se optó para ésto nuevamente por un Pipe, en el cual escribe el Jefe, y leen los Empleados (siendo que es necesario además utilizar un semáforo binario para poder sincronizar la lectura del pipe entre los N empleados).

\subsubsection{Empleados entre sí}
Nos interesa que mientras hayan surtidores libres, se pueda seguir accediendo a ellos, pero una vez que no hayan surtidores libres, los empelados se queden esperando a que tal situación cambie.\\
Se utilizará un semáforo inicializado con valor M (cantidad de surtidores). A medida que cada empelado desee usar un surtidor deberá hacer \textbf{wait} de tal semáforo, y al dejar de usar el surtidor, se deberá hacer \textbf{signal} para que otro empleado pueda utilizarlo.

Dado que además será necesario saber cuál surtidor se está agarrando en cada momento, tendremos un vector de M Memorias compartidas, de valores booleanos. Cada una de esas memorias compartidas representa a un surtidor, siendo que puede estar o no ocupado (originalmente están desocupados). Cuando un empleado quiere utilizar un surtidor, procede inicialmente como fue explicado en el párrafo anterior. Luego de poder acceder a los surtidores, necesariamente habrá algún surtidor libre (puesto que pasó por el semáforo en el cual su contador está directamente relacionado con la cantidad de surtidores libres). El empleado ve surtidor por surtidor hasta encontrar uno libre. Una vez que un empleado toma el surtidor debe establecer tal surtidor como \textbf{ocupado}. Al terminar de usarlo, pasa a marcarlo como \textbf{desocupado} (y recién ahí hace el \textbf{signal} del semáforo antes mencionado, para evitar problemas de concurrencia posibles).

\subsubsection{Empleados y Administrador}
Los empleados deberán, junto con el admintrador, utilizar sincronizadamente el dato del monto de la caja. Por lo tanto, suena casi automático pensar en una Memoria Compartida, de un valor flotante (puesto que se trata de dinero), sincronizada como ya fue mencioando.

\subsubsection{Comunicación para finalizar la simulación}
Quien se encarga de terminar la simulación (y hacerle llegar tal finalización al resto de los procesos) es la Estación de Servicio (que corresponde al proceso principal).

Dado que el Administrador se ejecuta de una manera casi completamente unilateral al resto de la simulación (más allá del sincronismo con los empleados), se decide optar por enviarle una señal al proceso del administrador, el cual tendrá el \textit{signal handler} correspondiente. El cual se comporta como en los casos de ejemplo de las clases prácticas de la materia (seteando una variable interna del objeto signal handler para luego poder hacer el \textit{gracefull quit}). De esta manera, la próxima vez que vea la caja, verá que le habían mandado la señal de finalización, terminando exitosamente su tarea.

A su vez, optamos por informale al generador que debe terminar de generar autos por el mismo método. El generador luego de enviar su último auto verá que le enviaron una señal (puesto que tiene su respectivo \textit{signal handler}), por lo que terminará su ejecución, cerrando previamente el Pipe de envíos hacia el Jefe. A partir de aquí se generará una reacción en cadena: cuando el jefe haya leido todos los autos que hayan quedado en el pipe, leerá un \textbf{EOF}, lo cual justamente implica que el generador no generará más autos. Entonces el jefe sabrá que su tarea también ha terminado, cerrando el Pipe de comunicación con los empleados (y también hacia el Pipe hacia el Generador), y terminando su ejecución. A su vez, los empleados seguirán atendiendo los autos, pero tarde o temprano cada uno de ellos leerá el \textbf{EOF} de su propio Pipe de comunicación con el Jefe, por lo que sabrán que su tarea también ha terminado, cerrando el Pipe mencionado, y terminando su ejecución. Notar que de ésta manera todos los procesos terminan su ejecución, habiendo atendido (o despachado) todos los autos que se hubieran creado por el generador hasta haber recibido la señal de finalización.
\newpage
\section{Diagramas de flujo de comunicación entre procesos}

\includegraphics[width=\textwidth]{clases.jpg} 
\newpage


\section{Diagramas de Transición de Estados}
\subsection{Jefe}

\end{document}